1. Field of the Invention
The present invention relates to routing packets in a telecommunications network, and, more particularly, to determining paths through nodes of the network for multicast routing of packets having guaranteed service levels.
2. Description of the Related Art
In interconnected packet networks, such as the Internet, users establish a connection between a source and a destination with a stream of data packets (called a xe2x80x9cpacket flowxe2x80x9d or xe2x80x9cflowxe2x80x9d) transferred through the network over a network path. The network path is defined by a set of nodes interconnected by a set of links. Packet networks may have a hierarchical structure in which smaller networks are interconnected by larger networks, and a peer structure in which equivalent networks are interconnected. A packet network connects to one or more other packet networks through ingress and egress points (routers) of the network.
FIG. 1 shows a network 100 of the prior art having nodes N1-N9 interconnected through links 101 that allow communication between packet networks 102-104. A router of node N1 that transfers packets to the network 100 from a source (packet network 102) is an example of an ingress point, and a router of node N4 that transfers packets from the network 100 to a destination (packet network 104) is an example of an egress point. The network 100 may support an interior routing protocol to distribute network topology information and route packets between ingress and egress points based on best-effort routing (e.g., destination-based shortest-path routing) through the nodes N1-N9. A centralized network management system 105 may be employed to 1) provision virtual circuits, or packet flows, through the network 100; 2) monitor capacity and utilization of links 101; and 3) coordinate calculation and installation of provisioned paths as router forwarding tables. Forwarding tables are used by each node""s router to forward each received packet to the next node in the path and toward its destination. In addition, the centralized network management system 105may collect and distribute network topology information.
Interior routing protocols are employed by network routers to determine a path through the nodes of the network along which packets between a source (ingress) and destination (egress) pair are forwarded. Packets received by a node""s router are forwarded to other nodes based on a forwarding table constructed in accordance with the interior routing protocol, but may also be through routes installed with explicit route provisioning. Interior routing protocols may also specify network topology and link-state information (xe2x80x9cnetwork topology informationxe2x80x9d) that is exchanged between the network nodes. Network topology information allows the node""s router to construct the corresponding forwarding table. An example of a widely used interior routing protocol for xe2x80x9cbest-effortxe2x80x9d routing is the Open Shortest Path First (OSPF) protocol. In addition, some routing protocols associate a link xe2x80x9ccostxe2x80x9d with each link between nodes. This link cost may be associated with, for example, average link utilization or revenue generated by the link, as well as link xe2x80x9cimportancexe2x80x9d in the network (i.e., how critical the link is to packet routing). When link-state information or link-bandwidth (e.g., connectivity or available bandwidth) is exchanged between routers, each router in the network has a complete description of the network""s topology.
Routing protocols, in addition to providing connectivity, may also enable traffic management. The Multi-Protocol Label Switched (MPLS) standard, for example, allows such routing protocols in networks. The MPLS standard may be employed for networks having virtual circuits (packet flows) or label switched paths (LSPs) with provisioned service levels (also known as guaranteed quality-of-service (QoS)).
Provisioned service levels may be, for example, a guaranteed minimum bandwidth for the path of a packet flow through the network. This path having a guaranteed level of service between ingress and egress points may be referred to as a Network Tunnel Path (NTP). As would be apparent to one skilled in the art, specific implementations of NTPs exist for different types of networks. As examples of NTPs, virtual circuits may be established for packet flows in TCP/IP networks, virtual circuits may be established for cells in Asynchronous Transfer Mode (ATM) networks, and label switched paths (LSPs) may be established for packets in MPLS networks. Packets of a signaling protocol, such as RSVP (Reservation Protocol for IP and MPLS networks) with traffic engineering extensions or CR-LDP (Constrained Routing Label Distribution Protocol for MPLS networks), may be used to reserve link bandwidth and establish an NTP. NTPs may be provisioned as an explicit route along specific paths between nodes of the network (i.e., when an NTP is provisioned, all intermediate points may be specified through which a packet passes between the ingress and egress points of the NTP).
In MPLS networks, packets are encapsulated by appending to the packet, or forming from the packet, additional information when the packet is received at an ingress point. The additional information, sometimes referred to as label, is then employed by routers of the network to forward the corresponding packet. In some cases, the label may simply be a pointer that identifies or is otherwise related to specific origination and termination address fields in the header of the received packet.
FIG. 2 shows such an encapsulated packet 200 having a label 201 appended to packet 202. The label summarizes information in the packet header 214 of the original packet 202. The summary may be based on the header field and includes a source address field (s) 210 identifying the address of the ingress point, a destination address field (r) 211 identifying the addresses of the egress point(s). For multicast packets, the destination address field 211 may represent a set Rs of receiver addresses rI through rK, each of which corresponds to a destination receiving the multicast connection""s packets. To distinguish between destinations of a unicast connection (single source and single destination) and those of a multicast connection (single source and multiple destinations), each destination of the multicast connection may be referred to as a xe2x80x9creceiver,xe2x80x9d though operations of a destination and a receiver are generally equivalent.
Label 201 also includes one or more service-level fields 212. Each service-level field 212 may identify a desired service level for the virtual circuit (called a xe2x80x9cdemandxe2x80x9d). In some networks, the values for the service-level fields, such as minimum bandwidth (b), may be implied or derived from the label itself. Other fields 213 may be included in label 201, such as MPLS standard version, interior routing protocol version, maximum delay, or other types of service-level parameters. Label 201 may alternatively be inserted into the packet header (PH) 214 of the packet 202, so the representation of fields shown in FIG. 2 is exemplary only. Networks may employ labels to group encapsulated packets having similar LSPs into classes (equivalence classes), and methods for forwarding equivalence classes may be employed to simplify calculation of NTP routing through the network.
To generate a forwarding table, each router computes a set of preferred paths through the network nodes, and may use weights to calculate the set of preferred paths. Each preferred path has a minimum total weight between nodes as well as minimum summed weight through nodes of the path, which is known in the art as shortest-path routing. This set of preferred paths may be defined with a shortest-path tree (SPT). The forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet to its destination along the shortest path of the SPT. The SPT may be calculated using an algorithm such as Dijkstra""s algorithm, described in E. Dijkstra, xe2x80x9cA Note: Two Problems In Connection With Graphs,xe2x80x9d Numerical Mathematics, vol. 1, 1959, pp. 269-271.
A common shortest-path routing algorithm to generate routing of an LSP is the min-hop algorithm. In the min-hop algorithm, each router calculates a path through the network for the stream of packets (packet flows) between the ingress and egress point. Each router constructs a path for routing the packet flow from the ingress point to the egress point with the least number (xe2x80x9cminxe2x80x9d) of feasible links (xe2x80x9chopsxe2x80x9d) (a feasible link is a link that exists and has sufficient capacity to route the packet flow). Routing schemes of the prior art, such as shortest-path routing, forward packets based only on destination addresses and use only static and traffic-characteristic-independent link weights to calculate paths for routing tables. Some links on the shortest path between certain pairs of ingress and egress points may be congested while other links on alternate paths are under-utilized. A signaling mechanism, such as RSVP or LDP, may be employed to both reserve and establish a connection through the network for a packet flow. The signaling mechanism may specify quality-of-service attributes for the NTP traversing the network.
In accordance with embodiments of the present invention, data of a multicast connection is routed along paths through a network of nodes interconnected by links from a source to a set of receivers based on a multicast routing tree. The multicast routing tree is generated by 1) forming a subnetwork of the network with nodes and links having available capacity for the multicast connection, and 2) routing the data between the source and each of the multicast receivers through corresponding paths. Routing of the data through the multicast routing tree selects corresponding paths based on a criterion that defers assigning the data to paths with relatively low available capacity or to paths that may be considered critical links. For some embodiments, a heuristic method determines the multicast routing tree by incrementally building a tree from the subnetwork formed by incrementally decreasing capacity of links. For other embodiments, a heuristic method determines the multicast routing tree by weighting the links of the subnetwork, and incrementally building a tree from paths from the source to each of the multicast receivers. The weights for links are determined from critical links in the subnetwork.
In accordance with an exemplary embodiment, data is routed from a source node to a plurality of receiver nodes, the source node and each receiver node included in a network of nodes interconnected by links. The outing is accomplished by (a) forming from the network of nodes and interconnected links, in response to a multi-cast routing request, a subnetwork having paths along which the data may be routed between the source node and the plurality of receiver nodes based on a service level of the routing request; (b) generating at least one tree, each tree comprising a set of nodes and links from the source node and the plurality of receiver nodes, wherein each tree is generated with link weights based on residual capacity of the links in the tree after the data is routed through the tree; (c) selecting a tree as the multicast routing tree, wherein the tree is selected based on a predetermined criteria; and (d) routing the data along the multicast routing tree.